package Hot100;

import LinkedList.ListNode;

public class 合并K个升序链表 {
    public ListNode mergeKLists(ListNode[] lists) {
        /* 自顶向下归并排序 */
        //return mergeSort(lists, 0, lists.length - 1);

        /* 自底向上归并排序 */
        int len = lists.length;
        if (len == 0) return null;
        if (len == 1) return lists[0];
        for (int newLen = len; newLen > 1; newLen = (newLen + 1) / 2) {
            for (int i = 0, j = 0; i < newLen; i += 2, j++) {
                if (i + 1 < newLen) lists[j] = merge(lists[i], lists[i + 1]);
                else lists[j] = merge(lists[i], null);
            }
        }
        return lists[0];
    }

    private ListNode mergeSort(ListNode[] lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return null;
        int mid = (l + r) >> 1;
        return merge(mergeSort(lists, l, mid), mergeSort(lists, mid + 1, r));
    }

    private ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) return head1 != null ? head1 : head2;
        ListNode dHead = new ListNode(-1);
        ListNode curr = dHead;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                curr.next = head1;
                head1 = head1.next;
            } else {
                curr.next = head2;
                head2 = head2.next;
            }
            curr = curr.next;
        }
        curr.next = (head1 != null ? head1 : head2);
        return dHead.next;
    }
}
